Graph Theory
Q12.
The following simple undirected graph is referred to as the Peterson graph.Which of the following statements is/are TRUE?MSQQ13.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1. Which of the statements above must necessarily be true?Q14.
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?Q15.
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?MSQQ16.
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .Q18.
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?Q19.
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?Q20.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ___________.